import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import DataModel.*;
public class GreedyForwardSelectionAlgorithm {

	public static double calculateInformationGain(
			HashMap<Integer, Movie> movies, ArrayList<Integer> featureIds) {

		int N = movies.size();
		double informationGain = 0.0;
		double entropy = 0.0;

		for (Integer featureId : featureIds) {
			double N_l = 0.0; // left node
			double N_r = 0.0; // right node

			for (Entry<Integer, Movie> movie : movies.entrySet()) {
				Movie tempMovie = movie.getValue();

				if (featureId == 1) {
					if (Integer.parseInt(tempMovie.features.get(featureId - 1).value) >= 100) {
						N_l += 1;
					} else {
						N_r += 1;
					}
				} else if (featureId == 20) {
					if (Double.parseDouble(tempMovie.features.get(featureId - 1).value) >= 3.0) {
						N_l += 1;
					} else {
						N_r += 1;
					}
				} else if (featureId == 21) {
					if (Integer.parseInt(tempMovie.features.get(featureId - 1).value) >= 2000000) {
						N_l += 1;
					} else {
						N_r += 1;
					}
				} else if (featureId == 22) {
					if (Integer.parseInt(tempMovie.features.get(featureId - 1).value) >= 2000) {
						N_l += 1;
					} else {
						N_r += 1;
					}
				} else {
					if (tempMovie.features.get(featureId - 1).value
							.equals("1")) {
						N_l += 1;
					} else {
						N_r += 1;
					}
				}
			}

			double P_l = N_l / N; // proportion of positive (training) examples
			double P_r = N_r / N; // proportion of negative (training) examples

			if ((P_l == 0.0) || (P_r == 0.0)) {
				entropy += 0.0;
			} else {
				entropy += -P_l * log2(P_l) - P_r * log2(P_r);
			}

			informationGain = 100.0 * (1.0 - entropy);

		}
		return informationGain;
	}

	public static double log2(double a) {
		return Math.log(a) / Math.log(2);
	}

	public static ArrayList<Integer> greedyForwardSelection(HashMap<Integer, Movie> movies) {

		HashMap<Integer, Double> informationGains = new HashMap<>();
		ArrayList<Feature> features = movies.get(1).features;
		ArrayList<Integer> featureIds = new ArrayList<>();
		ArrayList<Integer> bestFeatures = new ArrayList<>();
		double informationGain;
		double maxVal = Double.MAX_VALUE;
		int maxValIndex = 0;

		for (int index = 0; index < 15; index++){//
		//while (maxVal >= 50.0) {
			for (Feature feature : features) {

				if (feature.featureId != maxValIndex) {
					featureIds.add(feature.featureId);
				}

				for (int i = 0; i < bestFeatures.size(); i++) {
					featureIds.add(bestFeatures.get(i));
				}
			
				informationGain = calculateInformationGain(movies, featureIds);
				informationGains.put(feature.featureId, informationGain);

				featureIds = new ArrayList<>();
			}

			maxVal = Double.MAX_VALUE;
			for (int j = 1; j < informationGains.size(); j++) {
				if (informationGains.get(j) < maxVal) {
					if (bestFeatures.contains(j) == false) {
						maxVal = informationGains.get(j);
						maxValIndex = j;
					}
				}
			}
			
//			if(maxVal <= 50){
			bestFeatures.add(maxValIndex);
//			System.out.println("Iteration number: " + bestFeatures.size());
//			System.out.println("next best feature: " + (maxValIndex)
//					+ " informationGain: " + Math.round(maxVal) +"%");
//			}
			System.out.println();
		}
		return bestFeatures;
	}
	
	public static void main(String[] args){
		
		HashMap<Integer, Movie> movies = ReadData.getMoviesWithFeatures();
		ArrayList<Integer> bestFeatures = greedyForwardSelection(movies);
		
		System.out.println("Best Features: ");
		for(Integer featureId : bestFeatures){
			System.out.print(featureId + " ");
		}
		
		
	}
	

}
